/*
要求：股票问题，规定k次交易
策略：贪心+动态规划
 */
public class PriceTickets {

}
class PriceTicketsSolution {
    int res = 0;
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][n];//dp[i][j] 表示在prices[i...j]上交易一次最大收益
        for(int j=0;j<n;j++){
            for(int i=0;i<j;i++){
                int min = prices[i];
                for(int u=i+1;u<=j;u++){
                    dp[i][j] = Math.max(dp[i][j],prices[u]-min);
                    min = Math.min(prices[u],min);
                }
            }
        }//得到所有区间一次交易最大收益
        dfs(dp,k,0,0,0);//动态规划，在整个prices上找到小于K次交易最大收益
        return res;
    }
    void dfs(int[][] dp,int k,int count,int sum,int start){
        if(start==dp.length||count==k){
            res = Math.max(res,sum);
            return;
        }
        for(int i=start;i<dp.length;i++){
            if(dp[start][i]>0){
                dfs(dp,k,count+1,sum+dp[start][i],i+1);
            }
        }
    }
}